﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using WMM.Tapioca.Taxonomy;
using WMM.Tapioca.Linkbase;
using WMM.Tapioca.Validate;

namespace WMM.Tapioca.Linkbase
{
    /// <summary>
    /// XBRL 2.1 Specification 3.5.3.9.7.3
    /// The arcs expressed in the extended links within a DTS describe networks of relationships between XML fragments.
    /// This class represents an Network of Graph.
    /// </summary>
    public class NetworkGraph
    {
        private static readonly log4net.ILog log = log4net.LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);

        private Tuple<string, string, string, string> tupleNG;

        /// <summary>
        /// The tuple for this network of graph.
        /// </summary>
        public Tuple<string, string, string, string> TupleNG
        {
            get { return tupleNG; }
            set { tupleNG = value; }
        }

        private HashSet<Arc> networkRelationships;

        /// <summary>
        /// The Network Relationships of this grapf.
        /// </summary>
        public HashSet<Arc> NetworkRelationships
        {
            get { return networkRelationships; }
            set { networkRelationships = value; }
        }

        private List<Locator> distinctLocators;

        /// <summary>
        /// The list of distinct locators.
        /// </summary>
        public List<Locator> DistinctLocators
        {
            get { return distinctLocators; }
            set { distinctLocators = value; }
        }


        /// <summary>
        /// A collection of <see cref="Summation"/> objects that apply to this calculation link.
        /// </summary>
        public List<Summation> SummationConcepts
        {
            get;
            private set;
        }


        internal NetworkGraph(Tuple<string, string, string, string> tuple, HashSet<Arc> network, List<Locator> locators)
        {
           log.Debug("Creating a network graph: " + tuple.ToString() + " arcs count: " + network.Count);

           tupleNG = tuple;
           networkRelationships = network;
           distinctLocators = locators;
           this.SummationConcepts = new List<Summation>();
        }


        /// <summary>
        ///  A method that validate weather the linkbase document has directed cycle.
        /// </summary>
        public bool HasDirectedCycle()
        {
            // All Vertices in the Graph
            if (distinctLocators == null || distinctLocators.Count == 0)
            {
                return false;
            }

            Queue<Locator> q; // Queue will store vertices that have in-degree of zero
            long counter = 0;

            // Calculate the in-degree of all vertices and store on the Locator 
            foreach (Locator l in distinctLocators)
            {
                l.InDegree = 0;
            }

            foreach (Locator loc in distinctLocators)
            {
                foreach (Arc arc in loc.OutArcs)
                {
                    Locator toLocator = GetLocator(arc.ToLocator.Label);

                    if (toLocator != null)
                    {
                        toLocator.InDegree++;
                    }
                }
            }

            // Find all vertices with in-degree == 0 and put in queue 
            q = new Queue<Locator>();

            foreach (Locator loc in distinctLocators)
            {
                if (loc.InDegree == 0)
                    q.Enqueue(loc);
            }

            if (q.Count == 0)
            {
                return true; // Cycle found – all vertices have in-bound edges
            }
 
            // Traverse the queue counting Vertices visited 
            for (counter = 0; q.Count != 0; counter++)
            {
                Locator loc = q.Dequeue();

                foreach (Arc arc in loc.OutArcs)
                {
                    Locator to = GetLocator(arc.ToLocator.Label);

                    if (to != null)
                    {
                        to.InDegree--;

                        if (to.InDegree == 0)
                        {
                            q.Enqueue(to);
                        }
                    }
                }
            }

            if (counter != distinctLocators.Count)
            {
                return true;  //Cycle found
            }

            return false;
        }


        private bool[] marked;
        private Locator[] arcTo;
        private Stack<Locator> cycle_Renamed;


        /// <summary>
        ///  A method that verify weather the linkbase document has cycle, directed  or undirected.
        /// </summary>
        public bool  HasCycle()
        {
            // All Vertices in the Graph
            if (distinctLocators == null || distinctLocators.Count == 0)
            {
                return false;
            }

            marked = new bool[distinctLocators.Count];
            arcTo = new Locator[distinctLocators.Count];

            foreach (Locator loc in distinctLocators)
            {
                if (!marked[distinctLocators.IndexOf(loc)])
                {
                    Dfs(distinctLocators, null, loc);
                }
            }

            return cycle_Renamed != null;
        }


        private void Dfs(List<Locator> locators, Locator u, Locator v)
        {
            marked[distinctLocators.IndexOf(v)] = true;

            foreach (Locator loca in Adj(v))
            {

                // short circuit if cycle already found
                if (cycle_Renamed != null)
                {
                    return;
                }

                if (!marked[distinctLocators.IndexOf(loca)])
                {
                    arcTo[distinctLocators.IndexOf(loca)] = v;
                    Dfs(distinctLocators, v, loca);
                }
                else if (u != null && loca != u)  // check for cycle (but disregard reverse of edge leading to v)
                {
                    cycle_Renamed = new Stack<Locator>();

                    //for (Locator x = v; x != loca; x = arcTo[distinctLocators.IndexOf(x)])
                    //{
                    //    cycle_Renamed.Push(x);
                    //}

                    cycle_Renamed.Push(loca);
                    cycle_Renamed.Push(u);
                }
            }
        }


        /// <summary>
        /// Return the list of neighbors of locator loc as in Iterable. 
        /// </summary>
        public virtual List<Locator> Adj(Locator loc)
        {
            List<Locator> neighbors = new List<Locator>();

            foreach (var a in loc.OutArcs)
            {
                Locator locator = GetLocator(a.ToLocator.Label);

                if (locator != null)
                {
                    neighbors.Add(locator);
                }
            }

            foreach (var a in loc.InArcs)
            {
                Locator locator = GetLocator(a.FromLocator.Label);

                if (locator != null)
                {
                    neighbors.Add(locator);
                }
            }

            return neighbors;
        }


        private Locator GetLocator(string label)
        {
            //return distinctLocators.ContainsKeyByName(label.GetHashCode()) ? distinctLocators.GetItemByName(label.GetHashCode()) : null;

            foreach (Locator loc in distinctLocators)
            {
                if (loc.Label.Equals(label))
                {
                    return loc;
                }
            }

            return null;
        }



    }
}
